﻿#define _CRT_SECURE_NO_WARNINGS
//JZ57 和为S的两个数字
//题目
//题解(130)
//讨论(1k)
//排行
//面经new
//中等  通过率：30.94 % 时间限制：1秒  空间限制：64M
//知识点
//数学
//数组
//双指针
//描述
//输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。
//
//数据范围 :
//0
//≤
//�
//�
//�
//(
//	�
//	�
//	�
//	�
//	�
//)
//≤
//1
//0
//5
//​
//​
//
//0≤len(array)≤10
//5
//​​ ，
//1
//≤
//�
//�
//�
//�
//�
//[
//	�
//]
//≤
//1
//0
//6
//
//1≤array[i]≤10
//6
//
//示例1
//输入：
//[1, 2, 4, 7, 11, 15], 15
//复制
//返回值：
//[4, 11]
//复制
//说明：
//返回[4, 11]或者[11, 4]都是可以的
//示例2
//输入：
//[1, 5, 11], 10
//复制
//返回值：
//[]
//复制
//说明：
//不存在，返回空数组
//示例3
//输入：
//[1, 2, 3, 4], 5
//复制
//返回值：
//[1, 4]
//复制
//说明：
//返回[1, 4], [4, 1], [2, 3], [3, 2]都是可以的
//示例4
//输入：
//[1, 2, 2, 4], 4
//复制
//返回值：
//[2, 2]


class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array, int sum) {
        int left = 0;
        int length = array.size();
        int right = length - 1;
        vector<int> ret;
        while (left < right)
        {
            if (array[left] + array[right] > sum)
            {
                right--;
            }
            else if (array[left] + array[right] < sum) {
                left++;
            }
            else
            {
                ret.push_back(array[left]);
                ret.push_back(array[right]);
                break;
            }
        }

        return ret;
    }
};